Luogu P6669 [清华集训2016] 组合数问题 题解

发表于 更新于 分类于 阅读次数： 本文字数： 512 阅读时长 ≈ 1 分钟

Link

Description

给定 n,m,kn,m,k，对于所有的 0≤i≤n,0≤j≤min(i,m)0\le i \le n,0\le j \le min(i,m) 有多少对 (i,j)(i,j) 满足 Cijmod  k=0C_i^j \mod k = 0

1≤n,m≤1018, 1≤k≤1001\le n,m \le 10^{18},\ 1 \le k \le 100 且 kk 为质数。

Soluton

数位dp+Lucas定理

因为 kk 是质数，所以 Cnmmod  k≡Cnmod  kmmod  k×Cn/km/kmod  kC_n^m \mod k \equiv C_{n\mod k}^{m \mod k} \times C_{n/k}^{m/k} \mod k

又因为当 n<mn < m 时，Cnm=0C_n^m=0，就合法了。

因此我们只需要在数位dp时，记一下是否存在一位 ni<min_i < m_i。

这里数位dp时需要同时处理两个数，第二个数的边界也需要特殊处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long

using namespace std;

const int p = 1e9 + 7;
ll n, m, k;
int a[100], b[100], len;
ll f[100][2][2][2][2];

void init()
{
    scanf("%lld%lld", &n, &m);
    ll mx = max(n, m);
    len = 0;
    while(mx) len++, mx /= k;
    memset(a, 0, sizeof(a));
    for(int i = 1; i <= len; i++)
        a[i] = n % k, n /= k;
    memset(b, 0, sizeof(b));
    for(int i = 1; i <= len; i++)
        b[i] = m % k, m /= k;
    memset(f, -1, sizeof(f));
}

ll dfs(int cur, bool lima, bool limb, bool cmp, bool flag)
{
    if(~f[cur][lima][limb][cmp][flag]) return f[cur][lima][limb][cmp][flag];
    if(!cur) return flag;
    int upa = lima ? a[cur] : k - 1, upb = limb ? b[cur] : k - 1;
    ll res = 0;
    for(int i = 0; i <= upa; i++)
        for(int j = 0; j <= (cmp ? upb : min(i, upb)); j++)
            res = (res + dfs(cur - 1, lima & (i == upa), limb & (j == upb), cmp | (i > j), flag | (i < j))) % p;
    return f[cur][lima][limb][cmp][flag] = res;
}

int main()
{
    int T;
    scanf("%d%lld", &T, &k);
    while(T--)
    {
        init();
        printf("%lld\n", dfs(len, 1, 1, 0, 0));
    }
    return 0;
}